package company;

import java.util.Scanner;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 子数组 是数组中的一个连续部分。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 * <p>
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 */
public class MaxSubArray {
    public static void main(String[] args) {
        // 输入
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] split = s.replace("[", "").
                replace("]", "")
                .split(",");
        int len = split.length;
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }
        System.out.println(maxSubArray(nums));

    }

    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        // 定义dp
        int maxTotal = 0;
        int beforeTotal = 0;
        int temp = 0;

        // 分析dp：
        // 1）i数的和等于前i-1个数之和+num；存在一个判断，如果前i-1个数字之和小于0，那么可以舍弃，不参与到i数字和计算之中
        // 2) 标记dp中最大的值
        for (int i = 0; i < len; i++) {
            temp = Math.max(0, beforeTotal) + nums[i];
            if (temp > maxTotal) {
                maxTotal = temp;
            }
            beforeTotal = temp;
        }
        return maxTotal;
    }
}
